/*
Unique Paths II 
Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.
*/

class Solution {
public:
	int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
		
		int m = obstacleGrid.size();
		if (m == 0)
		{
			return 0;
		}
		int n = obstacleGrid[0].size();

		vector<int> levelNum(n,0);
		vector<vector<int> > setpTable(m, levelNum);

		//setpTable =obstacleGrid;

		if (obstacleGrid[0][0] == 0)
		{
			setpTable[0][0] = 1;
		
		}
		else
		{
			setpTable[0][0] = 0;
		}
		

		
		

		for (int i = 1; i <m; i++)
		{
			if (obstacleGrid[0][0] == 1)
			{
				break;
			}
			else
			{
				if (obstacleGrid[i][0] == 0)
				{
					setpTable[i][0] = 1;
				}else
				{
					//setpTable[i][0] = -1;
					break;
				}
			}

			
			
			
		}

		for (int i = 1; i <n; i++)
		{
			if (obstacleGrid[0][0] == 1)
			{
				break;
			}else
			{
				if (obstacleGrid[0][i] == 0)
				{
					setpTable[0][i] = 1;
				}else
				{
					//setpTable[i][0] = -1;
					break;
				}
			
			}

		}

		for (int i = 1; i < m; i++ )
		{
			for (int j = 1; j < n; j++)
			{
				if (obstacleGrid[i][j] == 1)
				{
					setpTable[i][j] = 0;
				}else
				{
					setpTable[i][j] = setpTable[i-1][j]+setpTable[i][j-1];
			
				} 
				
			}
		}

		return setpTable[m-1][n-1];

	}
};